/**
 * // Definition for a QuadTree node.
 * function Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
 *    this.val = val;
 *    this.isLeaf = isLeaf;
 *    this.topLeft = topLeft;
 *    this.topRight = topRight;
 *    this.bottomLeft = bottomLeft;
 *    this.bottomRight = bottomRight;
 * };
 */

function Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight) {
  this.val = val
  this.isLeaf = isLeaf
  this.topLeft = topLeft
  this.topRight = topRight
  this.bottomLeft = bottomLeft
  this.bottomRight = bottomRight
}

/**
 * @param {number[][]} grid
 * @return {Node}
 */
export var construct = function (grid) {
  const head = new Node()
  dfs(grid, head)
  return head
}

function dfs(grid, node) {
  if (grid.length === 1) {
    node.isLeaf = true
    node.val = grid[0][0]
    return
  }
  const n = grid.length
  let [tl, tr, bl, br] = [[], [], [], []]
  let sum = 0
  for (let i = 0; i < n / 2; i++) {
    tl.push([])
    tr.push([])
    bl.push([])
    br.push([])
    for (let j = 0; j < n / 2; j++) {
      tl[i].push(grid[i][j])
      tr[i].push(grid[i][j + n / 2])
      bl[i].push(grid[i + n / 2][j])
      br[i].push(grid[i + n / 2][j + n / 2])
      sum += grid[i][j] + grid[i][j + n / 2] + grid[i + n / 2][j] + grid[i + n / 2][j + n / 2]
    }
  }

  node.isLeaf = sum === 0 || sum === n * n
  node.val = sum > 0 ? 1 : 0
  if (node.isLeaf) return
  node.topLeft = new Node()
  node.topRight = new Node()
  node.bottomLeft = new Node()
  node.bottomRight = new Node()
  dfs(tl, node.topLeft)
  dfs(tr, node.topRight)
  dfs(bl, node.bottomLeft)
  dfs(br, node.bottomRight)
}
